package com.fw.algorithm.sort;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        int arr[] = {4, 6, 8, 5, 9};
        headSort(arr);
    }


    public static void headSort(int[] arr){
        int temp ;
      /*  adjustHeap(arr,1,arr.length);
        System.out.println(Arrays.toString(arr));*/

        // 置为 大顶堆
        for (int i = arr.length / 2 - 1;  i >=0; i--){
            adjustHeap(arr,i, arr.length);
        }
        System.out.println(Arrays.toString(arr));

        // 开始交换
        for(int j = arr.length-1;j >0; j--) {
      //交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }

        System.out.println(Arrays.toString(arr));
    }


    /**
     *
     * @param arr 需要排序的数组
     * @param i 叶子节点索引
     * @param length 排序的长度
     */
    public static void adjustHeap(int[] arr,int i ,int length){

        int temp = arr[i];

        for (int k = i * 2 + 1; k < length ; k = i * 2 + 1){
            // 次判断是用来 判断 字节点 左右两个值 是谁大
            if (k+1 < length && arr[k] < arr[k +1]){
                // 如果左边的值 小于 右边的值，进行指针移位。
                k ++;
            }
            if(arr[k] > temp) { //如果子结点大于父结点
                arr[i] = arr[k]; //把较大的值赋给当前结点
                i = k; //!!! i 指向 k,继续循环比较
            } else {
                break;//!
            }

            }
        arr[i] = temp;

    }
}


